package pl.ydp.components.mathcell.mathcell.preprocessing.multicharacter
{
	import flash.geom.Point;
	import flash.geom.Rectangle;
	
	import pl.ydp.components.mathcell.mathcell.preprocessing.structures.ArrayProcessor;
	import pl.ydp.components.mathcell.mathrecognizer.Debug;
	import pl.ydp.components.mathcell.mathrecognizer.engine.Parameters;
	import pl.ydp.components.mathcell.mathrecognizer.structures.Range;
	import pl.ydp.components.mathcell.mathcell.preprocessing.structures.VerticalLocation;
	
	/**
	 * Responsible for separating characeters.
	 */
	public class MultiCharacterSeparator
	{
		
		
		private static const CHARACTER_WIDTH_MIN:Number = 2;
		private static const SPACING_MIN_PROJECTION:Number = 4;
		private static const SPACING_MIN_DISTANCE_HORIZONTAL:Number = 6;
		private static const SPACING_MIN_DISTANCE_VERTICTAL:Number = 6;
		private static const OVERLAP_MARGIN_INTERNAL:Number = Parameters.CHAR_HEIGHT/15;
		private static const OVERLAP_MARGIN_EXTERNAL:Number = Parameters.CHAR_HEIGHT/40;
		
		public static function separate(_penPoints:Array, maxCharactersCount:Number, cellWidth:Number, cellHeight:Number, layout:Number):Array{
			
			if (_penPoints.length == 0)
				return new Array;
				
			if (_penPoints[0].length == 0)
				return new Array;
						
			var x:Array ;
			for each (x in _penPoints)	
				Debug.saveLog(x, "before MCC::separate()");
						
			var penPointsRanges:Array = findPenPointsRanges(_penPoints, layout);
			
			var penPointsBounds:Array = findPenPointsBounds(_penPoints, layout);
			
			var slashIndexPreDetection:Number = -1;
			
			if (layout == MultiCharactersLayout.VERTICAL  &&  _penPoints.length >= 3){
				var charactersPenPointsIndexesTestSlash:Array = separateCharacters(penPointsRanges, penPointsBounds, _penPoints, layout);
				if (charactersPenPointsIndexesTestSlash.length == 1){
					var allIndexes:Array = new Array;
					for (var i:Number = 0 ; i < penPointsRanges.length ; i ++)
						allIndexes.push(i);
					slashIndexPreDetection = detectSlash(_penPoints, allIndexes, penPointsRanges, cellWidth, cellHeight, VerticalLocation.MIDDLE);
				}
			}
			
			var charactersPenPointsIndexes:Array;
			
			if (layout == MultiCharactersLayout.VERTICAL  &&  _penPoints.length >= 3  && slashIndexPreDetection == -1){
				charactersPenPointsIndexes = charactersPenPointsIndexesTestSlash;
			} else {
				charactersPenPointsIndexes = separateCharacters(penPointsRanges, penPointsBounds, _penPoints, layout, slashIndexPreDetection);
			}
			
			if (slashIndexPreDetection != -1)
				charactersPenPointsIndexes.splice(1, 0, [slashIndexPreDetection]);
				
			
			var charactersBounds:Array;
						
			if (layout == MultiCharactersLayout.VERTICAL  &&  charactersPenPointsIndexes.length > 3){
				charactersBounds = findCharactersBounds(penPointsRanges, charactersPenPointsIndexes);
				charactersPenPointsIndexes = joinCharactersToLimit3( charactersBounds, charactersPenPointsIndexes);
			} else if (layout == MultiCharactersLayout.VERTICAL  &&  charactersPenPointsIndexes.length == 2){
				var slashIndexPostDetection:Number = detectSlash(_penPoints, charactersPenPointsIndexes[0], penPointsRanges, cellWidth, cellHeight, VerticalLocation.BOTTOM);
				var slashInCharacterIndex:Number = 0;
				if (slashIndexPostDetection == -1){
					slashIndexPostDetection = detectSlash(_penPoints, charactersPenPointsIndexes[1], penPointsRanges, cellWidth, cellHeight, VerticalLocation.TOP);
					slashInCharacterIndex = 1;
				}
				
				if (slashIndexPostDetection != -1){
					charactersPenPointsIndexes[2] = charactersPenPointsIndexes[1];
					charactersPenPointsIndexes[1] = new Array;
					charactersPenPointsIndexes[1].push(slashIndexPostDetection);
					
					if (slashInCharacterIndex == 1)
						slashInCharacterIndex = 2;
					
					var slashInCPPIndex:Number = (charactersPenPointsIndexes[slashInCharacterIndex] as Array).indexOf(slashIndexPostDetection);
					charactersPenPointsIndexes[slashInCharacterIndex].splice(slashInCPPIndex, 1);
				}
				
			}
			
			charactersBounds = findCharactersBounds(penPointsRanges, charactersPenPointsIndexes);
			
			var charactersPoints:Array = cloneCharactersPenPoints(_penPoints, charactersPenPointsIndexes);
			
			for each (x in charactersPoints[0])	
				Debug.saveLog(x, "after MCC::separate()");
				
			charactersPoints = sortCharacters(charactersPoints, charactersPenPointsIndexes, penPointsRanges, slashIndexPreDetection);
			
			charactersPoints = centerCharacters(charactersPoints, charactersBounds, layout, 
				(layout == MultiCharactersLayout.HORIZONTAL) ? cellWidth : cellHeight);
				
			
			//centerCharactersX();
			
			for each (x in charactersPoints[0])	
				Debug.saveLog(x, "after MCC::centerCharactersX()");
				
			return charactersPoints;
		}
		
		//-------------------------------------------------------------------
		
		private static function separateCharacters(penPointsRanges:Array, penPointsBounds:Array, penPoints:Array, layout:Number, ignoreStroke:Number = -1):Array{
			
			var r:Number;
			var ch:Number
			var stroke:Number;
			
			var slashY:Number = (ignoreStroke == -1) ? -1 : findMeanCoordY(penPoints[ignoreStroke]);
			
			// sort strokes by x			
			var sortedPenPointsIndexes:Array = findSortedPenPointsIndexes(penPointsRanges);
			
			var charactersPenPointsIndexes:Array = new Array();
			var charactersPenPointsIndexesUsed:Array = new Array();
			var charactersPenPointsIndexesUsedCount:Number = 0;
			
			charactersPenPointsIndexes.push(new Array);
			var firstStrokeAdded:Boolean = false;
			
			for (r = 0 ; r < penPointsRanges.length ; r ++){
				if (!firstStrokeAdded  &&  sortedPenPointsIndexes[r] != ignoreStroke){
					charactersPenPointsIndexes[0].push(sortedPenPointsIndexes[r]);
					firstStrokeAdded = true;
				}
				if (sortedPenPointsIndexes[r] == charactersPenPointsIndexes[0][0]  ||  (sortedPenPointsIndexes[r] == ignoreStroke)){
					charactersPenPointsIndexesUsed[sortedPenPointsIndexes[r]] = true;
					charactersPenPointsIndexesUsedCount++;
				}else{
					charactersPenPointsIndexesUsed[sortedPenPointsIndexes[r]] = false;
				}
			}
			
			// bug 33480 rozpoznawanie ułamków z więcej niż jedną cyfrą
			// jeżeli sprawdzane są dwa znaki, to potem może pojawić się
			// trzeci znak, który je połączy, a one będą już odseparowane
			// trzeba posortować znaki wg x, od lewej do prawej i sprawdzać
			// wg tego posortowania
			
			for (ch = 0 ; ch < penPointsRanges.length ; ch++){
				
				if (ch > 0)
					
					charactersPenPointsIndexes.push(new Array);
				
				for (r = 0 ; r < penPointsRanges.length ; r ++){
					if (charactersPenPointsIndexesUsed[sortedPenPointsIndexes[r]])
						continue;
					
					var add:Boolean = false;
					
					for each (var ppIndex:Number in charactersPenPointsIndexes[ch]){
						if (
							(
								layout == MultiCharactersLayout.HORIZONTAL  &&  
								(
									(penPointsRanges[ppIndex].min > penPointsRanges[sortedPenPointsIndexes[r]].max + SPACING_MIN_PROJECTION  &&  
										penPointsRanges[ppIndex].min > penPointsRanges[sortedPenPointsIndexes[r]].min + SPACING_MIN_PROJECTION + CHARACTER_WIDTH_MIN)
									||
									(penPointsRanges[ppIndex].max < penPointsRanges[sortedPenPointsIndexes[r]].min - SPACING_MIN_PROJECTION  &&  
										penPointsRanges[ppIndex].max < penPointsRanges[sortedPenPointsIndexes[r]].max - SPACING_MIN_PROJECTION - CHARACTER_WIDTH_MIN)
									//isRangesSeparated(penPointsRanges[ppIndex], penPointsRanges[sortedPenPointsIndexes[r]], false, true)
									||
									
										(
										isRangesSeparated(penPointsRanges[ppIndex], penPointsRanges[sortedPenPointsIndexes[r]], true, false)  &&
										!theseTwoAreDots(penPoints[ppIndex], penPoints[sortedPenPointsIndexes[r]])  &&  
										findDistance(penPoints[ppIndex], penPoints[sortedPenPointsIndexes[r]]) >= SPACING_MIN_DISTANCE_HORIZONTAL
										)
								)
							)
							||
							(
								layout == MultiCharactersLayout.VERTICAL  &&
								(isVerticallySeparated(ppIndex, sortedPenPointsIndexes[r], penPointsBounds, penPointsRanges) ||
								(slashY != -1  &&  isOnTheOtherSideOfSlash(slashY, penPointsRanges[ppIndex], penPointsRanges[sortedPenPointsIndexes[r]]))
								)
							)
						){
							// tested 'r' character DOES NOT overlap 'ppIndex' character
						} else {
							// tested 'r' character DOES overlap 'ppIndex' character
							add = true;
							break;
						}
					}
					
					if (add  ||  charactersPenPointsIndexes[ch].length == 0) {
						charactersPenPointsIndexes[ch].push(sortedPenPointsIndexes[r]);
						charactersPenPointsIndexesUsed[sortedPenPointsIndexes[r]] = true;
						charactersPenPointsIndexesUsedCount++;
					}
					
				}
				
				if (charactersPenPointsIndexesUsedCount == penPointsRanges.length)
					break;
			}
			
			return charactersPenPointsIndexes;
		}
		
		private static function findMeanCoordY(points:Array):Number{
			var meanY:Number = 0;
			
			for each (var p:Point in points){
				meanY += p.y;
			}
			
			return meanY/points.length;
			
		}
		
		private static function isOnTheOtherSideOfSlash(slashY:Number, refCharacterRange:Range, testCharacterRange:Range):Boolean{
			var refY:Number = (refCharacterRange.min + refCharacterRange.max)/2;
			var testY:Number = (testCharacterRange.min + testCharacterRange.max)/2;
			
			return (refY > slashY  &&  testY < slashY)  ||  (refY < slashY  &&  testY > slashY);
		}
			
		
		//-------------------------------------------------------------------
		
		private static function findPenPointsRanges(_penPoints:Array, layout:Number):Array{
			
			var penPointsRanges:Array = new Array();
			
			for (var stroke:Number = 0 ; stroke < _penPoints.length ; stroke++){
				var currRect:Rectangle = findBounds(_penPoints[stroke]);
				if (layout == MultiCharactersLayout.HORIZONTAL)
					penPointsRanges.push(new Range(currRect.left, currRect.right));
				else
					penPointsRanges.push(new Range(currRect.top, currRect.bottom));
			}
			
			return penPointsRanges;
		}
		
			
		private static function findSortedPenPointsIndexes(penPointsRanges:Array):Array{
			var sortedPenPointsIndexes:Array = new Array;
			
			var minCoordValue:Number;
			var minCoordIndex:Number;
			for (var pass:Number = 0 ; pass < penPointsRanges.length ; pass++){ 
				minCoordValue = 99999999;
				minCoordIndex = -1; 
				for (var stroke:Number = 0 ; stroke < penPointsRanges.length ; stroke++){
					if (penPointsRanges[stroke].min < minCoordValue  &&  sortedPenPointsIndexes.indexOf(stroke) == -1){
						minCoordValue = penPointsRanges[stroke].min;
						minCoordIndex = stroke;
					}
				}
				sortedPenPointsIndexes.push(minCoordIndex); 
			}
			
			return sortedPenPointsIndexes;
		}
		
		private static function findPenPointsBounds(_penPoints:Array, layout:Number):Array{
			var bounds:Array = new Array;
			
			for (var s:Number = 0 ; s < _penPoints.length ; s ++){
				bounds.push(new StrokeBounds(_penPoints[s], layout));
			}
			
			return bounds;
		}
		
		//-------------------------------------------------------------------
		
		private static function findDistance(refPoints:Array, testPoints:Array):Number{
			
			if (refPoints.length == 0  ||  testPoints.length == 0)
				return Infinity;
			
			var SEEK_STEP:Number = 8;
			var r:Number;
			var t:Number;
			
			var minDistanceRefIndex:Number = -1;
			var minDistanceTestIndex:Number = -1;
			var minDistance:Number = Infinity;
			var currDistance:Number;
			
			for (r = 0 ; r < refPoints.length ; r += SEEK_STEP ){
				for (t = 0 ; t < testPoints.length ; t += SEEK_STEP){
					currDistance = Point.distance(refPoints[r], testPoints[t]);
					if (currDistance < minDistance){
						minDistance = currDistance;
						minDistanceRefIndex = r;
						minDistanceTestIndex = t;
					}
				}
			}
			
			minDistance = Infinity;
			
			var rFrom:Number =  minDistanceRefIndex - SEEK_STEP
			if (rFrom < 0)
				rFrom = 0;	
			var rTo:Number = minDistanceRefIndex + SEEK_STEP;
			if (rTo > refPoints.length-1)
				rTo = refPoints.length-1;
			
			var tFrom:Number =  minDistanceTestIndex - SEEK_STEP
			if (tFrom < 0)
				tFrom = 0;	
			var tTo:Number = minDistanceTestIndex + SEEK_STEP;
			if (tTo > testPoints.length-1)
				tTo = testPoints.length-1;
		
			for (r = rFrom ; r <= rTo ; r ++){
				for (t = tFrom ; t <= tTo ; t ++){
					currDistance = Point.distance(refPoints[r], testPoints[t]);
					if (currDistance < minDistance){
						minDistance = currDistance;
					}
				}				
			}
			
			return minDistance;
		}
		
		//-------------------------------------------------------------------
		
		private static function isRangesSeparated(ref:Range, test:Range, useOverlapMargin:Boolean, useSpacing:Boolean):Boolean{
			
			var marginInternal:Number = (useOverlapMargin) ? OVERLAP_MARGIN_INTERNAL : 0;
			var marginExternal:Number = (useOverlapMargin) ? OVERLAP_MARGIN_EXTERNAL : 0;
			
			var spacingMin:Number = (useSpacing) ? SPACING_MIN_PROJECTION : 0;
			var spacingMinAndCharWidth:Number = (useSpacing) ? SPACING_MIN_PROJECTION+CHARACTER_WIDTH_MIN : 0;
			
			if (test.min > ref.max - marginInternal + spacingMin  &&  test.max >  ref.max - marginExternal  &&  test.min > ref.min + spacingMinAndCharWidth){
				return true;
			} else  if (ref.min > test.max - marginInternal + spacingMin  &&  ref.max >  test.max - marginExternal  &&  ref.min > test.min + spacingMinAndCharWidth){
				return true;
			}
			return false;
		}
		
		private static function theseTwoAreDots(refPoints:Array, testPoints:Array):Boolean{
			
			var refIsDot:Boolean = isDot(refPoints);
			var testIsDot:Boolean = isDot(testPoints);
			
			return refIsDot  &&  testIsDot;
		}
		
		public static function isDot(testPoints:Array):Boolean{
			var currPoint:Point;
			var testField:Rectangle = new Rectangle(testPoints[0].x, testPoints[0].y, 0.1, 0.1);
			for each (currPoint in testPoints){
				testField = testField.union(new Rectangle(currPoint.x, currPoint.y, 0.1, 0.1));
			}
			
			var ratio:Number = testField.width / testField.height;
			if (ratio < 1)
				ratio = 1 / ratio;
			
			if (testField.width < Parameters.DOT_MAX_SIZE  &&  testField.height < Parameters.DOT_MAX_SIZE  &&  ratio < Parameters.DOT_FIELD_COEFF_MAX){
				return true;
			}
			
			return false;
			
		}
		
		private static function isVerticallySeparated(refIndex:Number, testIndex:Number, penPointsBounds:Array, penPointsRanges:Array):Boolean{
			
			var distance:Number = penPointsBounds[refIndex].findDistance(penPointsBounds[testIndex]);
			
			var rangesSeparated:Boolean = isRangesSeparated(penPointsRanges[refIndex], penPointsRanges[testIndex], true, false);
			
			if (distance >= SPACING_MIN_DISTANCE_VERTICTAL  &&  distance != Infinity  &&  rangesSeparated)
				return true;
			
			if (distance == Infinity)
				return isRangesSeparated(penPointsRanges[refIndex], penPointsRanges[testIndex], false, true);
			
			return false;
		}
		
		//-------------------------------------------------------------------
		
		private static function findCharactersBounds(penPointsRanges:Array, charactersPenPointsIndexes:Array):Array{
			
			var charactersBounds:Array = new Array;
			
			for (var ch:Number = 0 ; ch < charactersPenPointsIndexes.length ; ch ++ ){
				var currBounds:Range = new Range(999999999, -999999999);
				
				for (var stroke:Number = 0 ; stroke < charactersPenPointsIndexes[ch].length ; stroke ++ ){
					if (currBounds.min > penPointsRanges[charactersPenPointsIndexes[ch][stroke]].min)
						currBounds.min = penPointsRanges[charactersPenPointsIndexes[ch][stroke]].min;
					if (currBounds.max < penPointsRanges[charactersPenPointsIndexes[ch][stroke]].max)
						currBounds.max = penPointsRanges[charactersPenPointsIndexes[ch][stroke]].max;
					
				}
				
				charactersBounds.push(currBounds);
			}
			
			
			return charactersBounds;
		}
		
		private static function joinCharactersToLimit3(charactersBounds:Array, charactersPenPointsIndexes:Array):Array{
			
			var pairOfCharacters:Array = findPairOfMinDistanceBetweenCharacters(charactersBounds);
			
			var newCharactersPenPointsIndexes:Array = internalMoveCharactersPenPointIndexes(charactersPenPointsIndexes, pairOfCharacters[1], pairOfCharacters[0]);

			return newCharactersPenPointsIndexes;
		}
		
		private static function findPairOfMinDistanceBetweenCharacters(charactersBounds:Array):Array{
			
			var currDistance:Number = Infinity;
			var refIndex:Number = 0;
			var testIndex:Number = 0;
			
			for (var ref:Number = 0 ; ref < charactersBounds.length ; ref ++){
				for (var test:Number = ref+1 ; test < charactersBounds.length ; test ++){
					if (charactersBounds[ref].max < charactersBounds[test].min){
						if (charactersBounds[ref].min - charactersBounds[test].max < currDistance){
							currDistance = charactersBounds[ref].max - charactersBounds[test].min;
							refIndex = ref;
							testIndex = test;
						}
					} else {
						if (charactersBounds[test].min - charactersBounds[ref].max < currDistance){
							currDistance = charactersBounds[test].max - charactersBounds[ref].min;
							refIndex = ref;
							testIndex = test;
						}
					}					
				}
			}
			
			return new Array(refIndex, testIndex);
		}
		
		private static function internalMoveCharactersPenPointIndexes(charactersPenPointsIndexes:Array, subjectIndex:Number, targetIndex:Number):Array{
			
			for each (var moved:Object in charactersPenPointsIndexes[subjectIndex]){
				charactersPenPointsIndexes[targetIndex].push(moved);
			}
			
			charactersPenPointsIndexes.splice(subjectIndex, 1);
			
			return charactersPenPointsIndexes;
		}
		
		//-------------------------------------------------------------------
		
		private static function detectSlash(penPoints:Array, charactersPenPointsIndexes:Array, penPointsRanges:Array, cellWidth:Number, cellHeight:Number, presumedSlashLocation:String):Number{
			
			var currIndex:Number;
			var inputMinCoord:Number = Infinity;
			var inputMaxCoord:Number = -Infinity;
			var searchMinCoord:Number;
			var searchMaxCoord:Number;
			var SLASH_ASPECT_MIN:Number = 3;
			var SLASH_WIDTH_MIN:Number = cellWidth/3;
			var SLASH_ENDING_DISTANCE_MIN:Number = cellHeight/12;
			
			for each (currIndex in charactersPenPointsIndexes){
				if (inputMinCoord > penPointsRanges[currIndex].min)
					inputMinCoord = penPointsRanges[currIndex].min;
				if (inputMaxCoord < penPointsRanges[currIndex].max)
					inputMaxCoord = penPointsRanges[currIndex].max;
			}
			
			if (presumedSlashLocation == VerticalLocation.TOP){
				searchMinCoord = inputMinCoord;
				searchMaxCoord = inputMinCoord + (inputMaxCoord - inputMinCoord)/3;
			} else if (presumedSlashLocation == VerticalLocation.BOTTOM){
				searchMinCoord = inputMinCoord + (inputMaxCoord - inputMinCoord)*2/3;
				searchMaxCoord = inputMaxCoord;
			} else if (presumedSlashLocation == VerticalLocation.MIDDLE){
				searchMinCoord = inputMinCoord + (inputMaxCoord - inputMinCoord)/3;
				searchMaxCoord = inputMaxCoord - (inputMaxCoord - inputMinCoord)/3;
			}
			
			var searchRange:Range = new Range(searchMinCoord, searchMaxCoord);
			
			var penPointsRangesHorizontal:Array = findPenPointsRanges(penPoints, MultiCharactersLayout.HORIZONTAL);
			var slashFound:Boolean;
			
			for each (currIndex in charactersPenPointsIndexes){
				var strokeWidth:Number = penPointsRangesHorizontal[currIndex].max - penPointsRangesHorizontal[currIndex].min;
				var strokeHeight:Number = penPointsRanges[currIndex].max - penPointsRanges[currIndex].min;
				
				if (strokeWidth/strokeHeight >= SLASH_ASPECT_MIN  &&  
					strokeWidth > SLASH_WIDTH_MIN  &&
					searchRange.contains(penPointsRanges[currIndex]) ){
					// sprawdzenie, czy nie ma połączeń pomiędzy końcami domniemanej kreski ułamkowej a innymi krzywymi
					
					var currIndex2:Number;
					var beginPoint:Point = penPoints[currIndex][0];
					var endPoint:Point = penPoints[currIndex][penPoints[currIndex].length-1];
					slashFound = true;
					
					for each (currIndex2 in charactersPenPointsIndexes){
						if (currIndex2 == currIndex)
							continue;
						
						if (Point.distance(beginPoint, penPoints[currIndex2][0]) < SLASH_ENDING_DISTANCE_MIN  ||
							Point.distance(beginPoint, penPoints[currIndex2][penPoints[currIndex2].length-1]) < SLASH_ENDING_DISTANCE_MIN  ||
							Point.distance(endPoint, penPoints[currIndex2][0]) < SLASH_ENDING_DISTANCE_MIN  ||
							Point.distance(endPoint, penPoints[currIndex2][penPoints[currIndex2].length-1]) < SLASH_ENDING_DISTANCE_MIN){
							slashFound = false;
							break;
						}
					}
				}
				
				if (slashFound)
					return currIndex;
			}
			
			return -1;
		}
		
		
		//-------------------------------------------------------------------
		
		private static function cloneCharactersPenPoints(penPoints:Array, charactersPenPointsIndexes:Array):Array{
			
			var charactersPoints:Array = new Array;
			
			for (var ch:Number = 0 ; ch < charactersPenPointsIndexes.length ; ch ++ ){
				charactersPoints.push(new Array);
				
				for (var stroke:Number = 0 ; stroke < charactersPenPointsIndexes[ch].length ; stroke ++ ){
					charactersPoints[ch].push(  ArrayProcessor.cloneRecursive( penPoints[charactersPenPointsIndexes[ch][stroke]] )  );
				}
				
			}
			
			return charactersPoints;
		}
		
		//-------------------------------------------------------------------
		
		private static function sortCharacters(charactersPoints:Array, charactersPenPointsIndexes:Array, penPointsRanges:Array, slashStrokeIndex:Number):Array{
			var output:Array = new Array;
			var ch:Number;
			var ch2:Number;
			var stroke:Number;
			var min:Number;
			var firstCoord:Number;
			var currCharacterIndex:Number;
			var used:Array = new Array;
			var slashCharacterIndex:Number = -1;
			
			for (ch = 0 ; ch < charactersPoints.length ; ch ++){
				if (charactersPenPointsIndexes[ch].length == 1  &&  charactersPenPointsIndexes[ch][0] == slashStrokeIndex){
					used.push(true);
					slashCharacterIndex = ch;
				} else {
					used.push(false);
				}
			}
			
			for (ch = 0 ; ch < charactersPenPointsIndexes.length ; ch ++){
				min = Infinity;
				currCharacterIndex = -1;
				
				for (ch2 = 0 ; ch2 < charactersPenPointsIndexes.length ; ch2 ++){
					
					if (used[ch2])
						continue;
					
					for (stroke = 0 ; stroke < charactersPenPointsIndexes[ch2].length ; stroke ++){
						firstCoord = penPointsRanges[charactersPenPointsIndexes[ch2][stroke]].min;	
						if (firstCoord < min){
							currCharacterIndex = ch2;
							min = firstCoord;
						}					
					}					
				}
				
				if (currCharacterIndex != -1){
					output.push(charactersPoints[currCharacterIndex]);
					used[currCharacterIndex] = true;
				}
			}
			
			if (slashCharacterIndex != -1){
				output.splice(1, 0, charactersPoints[slashCharacterIndex] );
			}
			
			return output;
			
		}
		//-------------------------------------------------------------------
		private static function findBounds(stroke:Array):Rectangle{
			if (stroke.length == 0)
				return new Rectangle(0,0,0,0);
			
			var min:Point = new Point(999999999,999999999);
			var max:Point = new Point(-999999999,-999999999);
			
			for each (var p:Point in stroke){
				if (p.x > max.x)
					max.x = p.x;
				if (p.y > max.y)
					max.y = p.y;
				if (p.x < min.x)
					min.x = p.x;
				if (p.y < min.y)
					min.y = p.y;
			}
				
			var rect:Rectangle = new Rectangle(min.x, min.y, max.x - min.x, max.y - min.y) ;
			
			return rect;
		}
		//-------------------------------------------------------------------
		
		
		private static function centerCharacters(charactersPoints:Array, charactersBounds:Array, layout:Number, cellWidthOrHeight:Number):Array{
			
			var ch:Number;
			var stroke:Number;
			
			//var centerX:Number;
			var currOffset:Number;
			var currCharWidthOrHeight:Number;
			
			//_characterOffsetsX = new Array;
			
			for (ch = 0 ; ch < charactersPoints.length ; ch++){
				
				currCharWidthOrHeight = charactersBounds[ch].max - charactersBounds[ch].min;
				//centerX = charactersBounds[ch].min + currCharWidth/2;
				currOffset = charactersBounds[ch].min - (cellWidthOrHeight - currCharWidthOrHeight)/2;
				
				//for each (var charArr:Array in _charactersPoints)
					for each (var strokeArr:Array in charactersPoints[ch])
						for each (var p:Point in  strokeArr){
							if (layout == MultiCharactersLayout.HORIZONTAL)
								p.x -=  currOffset;
							else
								p.y -=  currOffset;
						}
						
				//_characterOffsetsX.push(currOffset);
				
				
			}
			
			return charactersPoints;
		}

	}
}